1. Field of the Invention
The present invention is directed to internetworking systems and in particular to methods and apparatuses for managing traffic flow in routers and switches.
2. Description of Related Art
Internetworking encompasses all facets of communications between and among communication networks. Such communications may include voice, video, still images, and data traffic. All communications have widely varying needs in terms of propagation delay (or latency) during transit through the network. Various systems and devices, both in hardware and in software, have attempted to deal with the plethora of data flow requirements present in modern internetworking systems.
In a communications network, routing devices receive communications at one of a set of input interfaces and forward them to one of a set of output interfaces. For a publication describing routing devices, see Chapter 7 of “Interconnection Networks: An Engineering Approach” by Jose Duato, Sudhakar Yalamanchili and Lionel Ni, published by IEEE Computer Society Press, Los Alamitos, Calif., 1997, which is incorporated by reference herein in its entirety.
Users typically require that such routing devices receive and forward communications as quickly as possible. In a packet routing network, where communications are transmitted in discrete portions or “packets” of data, each packet includes a header. The header contains information used for routing the packet to an output interface and subsequent forwarding to a destination device. The packet may also be forwarded to another router for further processing and/or forwarding. Header information used for routing may include the destination address and source address for the packet. Additionally, header information such as the destination device port, source device port, protocol, packet length, and packet priority may be used. Header information used by routing devices for administrative tasks may include information about access control, accounting, quality of service (QoS), or class of service (CoS). Herein, a “packet” is any grouping of one or more data elements of any size, including data cells and data bytes, and encoded using any protocol.
FIG. 1 depicts a generic packet routing/switching system 100 that will be used to describe both the prior art and embodiments of the invention. A well-known routing device or switch 100 includes: multiple linecards 110-0 to 110-X coupled to a switch fabric 120, which provides communications between one or multiple linecards 110. Herein “linecard 110” refers to any of linecards 110-0 to 110-X unless otherwise specified. Each linecard 110 includes an input interface 111, an output interface 112, a fabric interface 170, and a control element 130. Each linecard 110 connects to communications network 50, which may be any form of local, enterprise, metropolitan, or wide area network known in the art, through both input interface 111 and output interface 112.
A “port” can correspond to a fraction of the total bandwidth of input interface 111 or output interface 112. Alternatively, a “port” can correspond to the total bandwidth of input interface 111 or output interface 112.
Control element 130 is configured to receive inbound packets 113 (i.e., packets entering the system from network 50) from input interface 111, process each packet, and transmit it through fabric interface 170 to switching fabric 120 through which it is sent to another (or the same) linecard 110 for further processing. Control element 130 includes ingress receiver 140, input traffic manager 150, output traffic manager 160, and egress transmitter 180.
The ingress receiver 140 operates in conjunction with lookup circuit 145 (both of control element 130) to determine routing treatments for inbound packets 113. Lookup circuit 145 includes routing treatment information disposed in a memory data structure. Access and use of this information in response to data in the header of inbound packet 113 is accomplished with means well-known in the router art. These routing treatments can include one or more of the following:                selection of one or more output interfaces (e.g., particular line card 110 and port to the network 50) to forward inbound packets 113 based on either a destination device field, source and destination device fields, or information in any other packet header fields;        determination of whether to drop (i.e., not forward) inbound packets 113;        determination of access control list (ACL) treatment for inbound packets 113:        determination of class of service (CoS) treatment for inbound packets 113;        determination of virtual private network (VPN) treatment for inbound packets 113;        determination of one or more accounting records or treatments for inbound packets 113; and/or        determination of other administrative treatment for inbound packets 113.        
Examples of such routing systems may be found in U.S. Pat. No. 5,088,032, entitled “Method and Apparatus for Routing Communications Among Computer Networks” to Leonard Bosack; U.S. Pat. No. 5,509,006, entitled “Apparatus and Method for Switching Packets Using Tree Memory” to Bruce Wilford et al.; U.S. Pat. No. 5,852,655, entitled “Communication Server Apparatus Having Distributed Switching and Method” to John McHale et al.; and U.S. Pat. No. 5,872,783, entitled “Arrangement for Rendering Forwarding Decisions for Packets Transferred Among Network Switches” to Hon Wah Chin, all incorporated herein by reference in their entireties.
The input traffic manager 150 receives inbound packets 113 from the ingress receiver 140 and provides inbound packets 113 to the switching fabric 120. Input traffic manager 150 selectively buffers inbound packets 113 when the switching fabric 120 is too congested with packets that it cannot receive inbound packets 113. For examples of input traffic manager 150 and output traffic manager 160, see U.S. Pat. No. 5,926,458, entitled “Method and Apparatus for Servicing Multiple Queues,” to Yin, U.S. Pat. No. 5,838,994, entitled “Method and Apparatus for the Dynamic Allocation of Buffers in a Digital Communications Network” to Valizadeh, and U.S. Pat. No. 5,689,505, entitled “Buffering of Multicast Cells in Switching Networks” to Chiussi, et al., which are all incorporated herein by reference in their entireties.
Output traffic manager 160 is similar to input traffic manager 150 except output traffic manager 160 receives outbound packets 114 from the switching fabric 120, via the fabric interface 170, and selectively buffers outbound packets 114 when the network 50 is so congested that it cannot receive outbound packets 114 (so called “output buffering scheme”).
Conventional egress transmitter 180 manages transmission of outbound packets 114 from the output traffic manager 160 to network 50.
One problem with switching fabric 120 occurs when packets from multiple input ports to switching fabric 120 are addressed to the same output port of the switching fabric 120 (so called “contention”). Consequently, packets from some input ports are delayed access to the output port.
One solution to contention is called “speed up.” For example, when packets from N input ports to switching fabric 120 are destined for the same output port of switching fabric 120, a speed up of X times the nominal packet speed through all transmission lines between input and output ports of the switching fabric 120 is used. Thereby, X packets now traverse the switching fabric 120 in the same time that 1 packet traversed the switching fabric 120 prior to speed up. However, “speed up” is not economical for very high line speeds.
Where packets are directed to specified output ports, certain ports may become overloaded with traffic beyond the speed up of the fabric, resulting in other ports which share fabric resources being “starved” from receiving data. For high line speeds, increasing the speed up would not be an economical solution.
Thus what is needed is a method and apparatus to reduce contention of packets input to a switching fabric and a network.